#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include <string.h>
#include "HFtree.h"
#include <stdlib.h>


// 颠倒二维数组每一行中不为 '\0' 的元素顺序
void reverse_non_zero_elements(char** arr, int rows, int cols) 
{
    for (int i = 0; i < rows; i++) 
    {
        int start = 0;
        int end = cols - 1;//定义两个指针指向首尾同时进行加减

        while (start < cols && arr[i][start] == '\0') 
        {
            start++;
        }
        while (end >= 0 && arr[i][end] == '\0') 
        {
            end--;
        }
        while (start < end) 
        {
            char temp = arr[i][start];
            arr[i][start] = arr[i][end];
            arr[i][end] = temp;

            start++;
            end--;

            while (start < cols && arr[i][start] == '\0') 
            {
                start++;
            }
            while (end >= 0 && arr[i][end] == '\0') 
            {
                end--;
            }
        }
    }
}

//打印编码的结果
void Code_print(HuffmanTree tree,int num,int* count,char** arr, char* code_arr)
{
    int i = 0;
    for (i = 0; i < 2 * num - 1; i++)
    {
        if (i < 2 * num - 2)//由于我使用了数组第一个元素，所以需要对数组进行处理才能显示书上的结果
        {
            if(i < num)
            {             
                printf("%d %d %d %d %d\n", i + 1, tree[i].weight, tree[i].parent + 1, tree[i].lchild, tree[i].rchild);
            }
            else
            {
                printf("%d %d %d %d %d\n", i + 1, tree[i].weight, tree[i].parent + 1, tree[i].lchild + 1, tree[i].rchild + 1);
            }
        }
        else
        {
            printf("%d %d %d %d %d\n", i + 1, tree[i].weight, tree[i].parent, tree[i].lchild + 1, tree[i].rchild + 1);
        }
    }

    int k = 0;
    for (i = 0; i < 26; i++)//显示不同字符的编码
    {
        if (count[i] != 0)
        {
            printf("%c:", i + 'a');
            int j = 0;
            for (j = 0; j < num; j++)
            {
                printf("%c", arr[k][j]);
            }
            k++;
            printf(" ");
        }
    }
    printf("\n");
    k = 0;
    int n = 0;
    int m = 0;
    for (i = 0; i < 26; i++)//显示编码后的二进制表达式
    {
        if (count[i] != 0)
        {
            int j = 0;
            for (n = 0; n < count[i]; n++)
            {
                for (j = 0; j < num; j++)
                {
                    printf("%c", arr[k][j]);
                    if (arr[k][j] != '\0')
                    {
                        code_arr[m] = arr[k][j];
                        m++;
                    }
                }
             
            }
            k++;
        }
    }

}


int main()
{
	int i = 0;
	int num = 0;
    int input_num = 0;
    int loop = 0;
	char str[MAX_SIZE][MAX_SIZE];//定义一个存放每一行输入的二维数组
	int count[26] = { 0 };
    char getcode_arr[MAX_SIZE] = {0};
	HuffmanTree tree = NULL;

    while (1)
    {
        scanf("%s",str[input_num]);
        if (str[input_num][0] == '0')
        {
            break;
        }
        else
            input_num++;
    }
    for (loop = 0;loop < input_num;loop++)//输入了input_num有效行
    {
        num = alphabet(str[loop], count);
        char* code_str = (char*)malloc(sizeof(char) * num);
        char** arr = (char**)malloc(sizeof(char*) * num); //定义一个二维数组存放num个叶子的编码，共num行
        for (i = 0; i < num; i++)
        {
            arr[i] = (char*)malloc(num * sizeof(char));//二叉树最大深度为num，一行就最大num个元素
        }
        for (int i = 0; i < num; i++)
        {
            memset(arr[i], '\0', num * sizeof(char));  // 初始化每一行
        }
        tree = tree_Create(num);
        tree_Voluate(tree, count);
        HFtree_Build(tree, num, code_str,count);
        HFtree_Code(tree, num, arr);
        reverse_non_zero_elements(arr, num, num);
        Code_print(tree, num, count, arr,getcode_arr);
        printf("\n");
        HuffmanDeCode(tree, getcode_arr, code_str,num);

        for (i = 0; i < 26; i++)
        {
            count[i] = 0;
        }

        for (i = 0; i < num; i++)
        {
            code_str[i] = 0;
        }

        for (i = 0; i < MAX_SIZE; i++)
        {
            getcode_arr[i] = 0;
        }
    }

	return 0;
}